In order to apply a cryptographic calculation to a message, conventionally algorithms are employed for inserting arbitrary values into mathematical structures. For this purpose, the elliptical curves are mathematical structures that are able to facilitate the application of such cryptographic calculations and at the same time save space in memory relative to the use of other cryptographic calculations.
However, efficient algorithms for inserting arbitrary values using elliptical curves are probabilistic. Consequently, the application time of these algorithms is not constant, it depends on the message to be encoded. Thus, if an attacker determines different application times of the algorithm applied, he can obtain information about the coded message.
In order to mask the time taken by a probabilistic insertion algorithm, it is possible to provide the addition of unnecessary steps in this algorithm so that its application always extends over a period of time of identical length, regardless of the message processed.
A point P of an elliptical curve is defined by its abscissa X and its ordinate Y, X and Y satisfying the following equation:f(X)=Y2  (1)                where f(X) is the polynomial f(X)=X3+aX+b        
A family of polynomials is known, which satisfy Skalba's equality which makes it possible to determine such a point on an elliptical curve, as defined in the document ‘Construction of Rational Points on Elliptic curves over finite fields’ by Andrew Shallue and Christiaan van de Woestijne.
Polynomials X1(t), X2(t), X3(t) and U(t) satisfy Skalba's equality if they satisfy the following equation:f(X1(t))·f(X2(t))·f(X3(t))=U2(t)  (2)
where f is the function that defines the elliptical curve under consideration, and
where t is a parameter.
The polynomials that satisfy Skalba's equality can take two parameters u and t. In this case, Skalba's equality is written:f(X1(t,u))·f(X2(t,u))·f(X3(t,u))=U2(t,u)
Equations of this type can be used with two parameters u and t. However, in the proposed applications, we can advantageously envisage setting u, or alternatively setting t, at any value. Thus, the value of a single parameter remains to be chosen.
Given selected parameters t and u, it is noted that X1=X1(t,u), X2=X2(t,u), X3=X3(t,u), U=U(t,u), where X1, X2, X3 and U are elements of Fq. This equation (2) signifies that at least one of the values f(X1), f(X2) and f(X3) corresponds to a squared term in the finite field Fq.
Then, once the squared term in Fq, f(Xi), is identified, we can then obtain a point on the elliptical curve P(Xi,√{square root over (f(Xi))}.
Calculation of √{square root over (f(Xi))} can be performed by means of an exponentiation calculation when the characteristic q of the field Fq satisfies:q=3 mod 4
In this case, it is known that:√{square root over (f(Xi))}=f(Xi)(q+1)/4  (3)
In order to determine a point on the elliptical curve (1), it is therefore necessary to determine which value among the three values f(X1), f(X2) and f(X3) corresponds to a squared term in the finite field Fq. For this purpose we could envisage checking firstly whether the term f(X1) is a squared term in the finite field Fq, then, if it is not the case, apply this same check to the term f(X2), and finally if this is still not so, check the term f(X3) similarly. However, following this procedure, determination of a point on the elliptical curve does not always take the same time, since this determination is executed more quickly if the first term tested is a squared term than if only the third term is a squared term.
A potential attacker could make use of this difference in elapsed time to determine a point on the elliptical curve for breaking the secret linked to the parameter that enabled this point to be generated. Now, in the field of cryptography, these parameters must remain secret.
These parameters can in particular correspond to passwords. Thus, it is important that determination of these points does not in itself supply information that makes it possible to break the secret of the parameter, and accordingly, attacks based on an analysis of the elapsed time for determining a point on the curve are to be avoided.
To overcome this disadvantage, it would be possible to check the three terms f(Xi) systematically for i in the range from 1 to 3. Thus, the time for determining a point on the curve would no longer be a function of the point determined.
However, checking whether a term of equation (2) is a squared term in the finite field Fq is a complex operation in particular employing an exponentiation, which is costly in execution time. In the case when we wish to determine a point on an elliptical curve on the basis of Skalba's equalities, while performing these determinations in a constant time, four operations of exponentiation are required in the case described above, one exponentiation per check of each of the terms of Skalba's equation (2) and one exponentiation for calculating the square root, as described in equation (3).
The present invention aims to improve this situation.